class Solution {
public:
    //dp[i][j]表示以i位置开始，j位置结束的字串是否是回文串(1/0)
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));    

        int ret = 0;
        for (int j = 0; j < n; j++)
        {
            for (int i = j; i >= 0; --i)
            {
                if (i == j)
                    dp[i][j] = 1;
                else
                {
                    if (s[i] == s[j] && (dp[i + 1][j - 1] == 1 || j - i == 1))
                        dp[i][j] = 1;
                }
                ret += dp[i][j];
            }
        }



        return ret;
    }
};